package com.zhaopin.mianshi;

/**
 * @author yin.peide
 * @date 2021-05-17 14:12
 * 求二维数组 最小路径之和
 */
public class Eerchashu {


    public static void main(String[] args) {
        int[][] attr = {{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}};

        Eerchashu eerchashu = new Eerchashu();
        System.out.println(eerchashu.minPathSum(attr));
    }

    /**
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */

    public int minPathSum(int[][] matrix) {

        int[][] dp = new int[matrix.length][matrix[0].length];
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < matrix.length; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }
        for (int i = 1; i < matrix[0].length; i++) {
            dp[0][i] = dp[0][i - 1] + matrix[0][i];
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[matrix.length - 1][matrix[0].length - 1];

    }
}
